#pragma once
#include <iostream>

using namespace std;

namespace dzp
{
    template<class K ,size_t M>
    struct BTreeNode
    {
        K keys[M];   //M-1 个关键字 +1用来保存满时的关键字
        BTreeNode<K,M>* child[M+1]; //M个子树，因为多一个关键字 
        BTreeNode<K,M>* parent;
        size_t n;//记录保存了几个关键字

        BTreeNode()
        {
            for(size_t i=0;i<M;i++)
            {
                keys[i]=K();
                child[i]=nullptr;
            }
            child[M]=nullptr;
            parent=nullptr;
            n=0;
        } 
    };

    //K是关键字类型 M是几阶树
    template<class K,size_t M>
    class BTree
    {
        typedef struct BTreeNode<K,M> Node;
        public:

        pair<Node*,int> Find(const K& key)
        {
            Node* parent=nullptr;
            Node* cur=root;
            while(cur)
            {
                int i=0;
                while(i<cur->n)
                {
                    if(key<cur->keys[i])
                    {
                        break;
                    }else if(key==cur->keys[i])
                    {
                        return make_pair(cur,i);
                    }else
                    {
                        ++i;
                    }
                }
                parent=cur;
                cur=cur->child[i];
            }
            return make_pair(parent,-1);
        }

        void InsertKey(Node* node,const K& key,Node* child)
        {
            size_t end=node->n-1;
            while(end>=0 )
            {
                //key比keys[end]大 后移
                if(key<node->keys[end])
                {
                 node->keys[end+1]=node->keys[end];
                 //添加的节点必然是小于 child[end+1] 
                 node->child[end+2]=node->child[end+1];  
                 --end;
                }else if(key>node->keys[end])
                break;
            }
            node->keys[end+1]=key;//1中是 i为-1，2>=0 如果是分裂的必然是孩子大于child[i] 
            node->child[end+2]=child;//所以 就只需要移动i 后面的孩子
            if(child)
            {
                child->parent=node;//分裂的出来的孩子节点的父亲
            }
            node->n++;

        }
        bool Insert(const K& key)
        {
            if(root==nullptr)
            {
                root=new Node;
                root->keys[0]=key;
                root->n++;
                return true;
            }
            pair<Node* ,int> cur=Find(key);
            if(cur.second>=0)
            return false;

            //添加叶子节点
            Node* tmp=cur.first;
            K newkey=key;
            Node* child=nullptr;
            while(1)
            {
                //添加加叶子或分裂出来的右孩子
                InsertKey(tmp,newkey,child);
                if(tmp->n<M)
                    return true;
                else 
                {
                    Node* brother=new Node;
                    int j=0;
                    int min=M/2;
                    int i=min+1;
                    for(;i<=M-1;++i)
                    {
                        brother->keys[j]=tmp->keys[i];
                        brother->child[j]=tmp->child[i];
                        tmp->keys[i]=K();
                        tmp->child[i]=nullptr;
                        //在父节点分裂时 要把孩子节点得父亲节点改变了
                        if(brother->child[i])
                            brother->child[i]->parent = brother;

                        ++j;                       
                    }
                    brother->child[j]=tmp->child[i];//最后得孩子节点转移
                    tmp->child[i]=nullptr;
                    if(brother->child[i])
                        brother->child[i]->parent = brother;
                    
                    brother->n=j;
                    tmp->n-=(brother->n+1);

                    K minkey=tmp->keys[min];
                    tmp->keys[min]=K();

                    //把中间值向上传
                    if(tmp->parent==nullptr)
                    {
                        root=new Node;
                        root->keys[0]=minkey;
                        root->child[0]=tmp;
                        tmp->parent=root;
                        root->child[1]=brother;
                        brother->parent=root;
                        root->n++;
                        break;
                    }else
                    {
                        //父亲节满了
                        newkey=minkey;
                        child=brother;
                        tmp=tmp->parent;
                    }
                }
            }
            return true;
        }
        void _InOrder(Node* pRoot)
         {
          if (NULL == pRoot)
              return;
          for (size_t i = 0; i < pRoot->n; ++i)
         {
             _InOrder(pRoot->child[i]);
            cout << pRoot->keys[i] << " ";
          }
         _InOrder(pRoot->child[pRoot->n]);
        }
        
        void InOrder()
        {
         _InOrder(root);
         }
        private:
        Node* root=nullptr;
    };
}